Problems tagged with "loop invariants"

Consider iterative_binary_search below and note the print statement in the while-loop:

import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Suppose iterative_binary_search is run on the array:

[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]

with target 11.

What will be the last value of arr[start] printed?

Consider the iterative implementation of binary search shown below:

import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Which of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.

Suppose you are sorting an array using selection sort. At the current iteration of selection sort, the array being sorted looks like this:

[0, 1, 2, 2, 3, 4, 2, 10, 13, 4]

Which of the following are possible options for how many times the outer for loop has run? Select all that apply.

Consider the following code, which takes in a list of integers and moves all of the odd numbers to the front and all of the even numbers to the end, in-place.

Remember that the \(\%\) operator computes the remainder of division. For example \(5 \% 2 = 1\) and \(4 \% 2 = 0\). This can be used to check if a number is even; if \(x \% 2 = 0\), then x is even.

def separate_odd_from_even(numbers):
    """Moves the odd numbers to the front, in-place."""
    n = len(numbers)

    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    odd_barrier = 0
    even_barrier = n - 1

    while odd_barrier < even_barrier:
        if numbers[odd_barrier] % 2 == 0:
            # the number is even
            swap(odd_barrier, even_barrier)
            even_barrier -= 1
        else:
            # the number is odd
            odd_barrier += 1

Consider this code which partitions a list in a special way:

def is_even(i):
    """Returns True if i is even, False otherwise."""
    return i % 2 == 0

def mystery_partition(numbers):
    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    barrier_ix = 0
    for i in range(len(numbers)):
        if is_even(numbers[i]):
            swap(i, barrier_ix)
            if numbers[barrier_ix] > numbers[0]:
                swap(0, barrier_ix)
            barrier_ix += 1

Which of the following loop invariants are true for this code? Select all that apply.

Note: any statement about an empty set or list is considered to be automatically true.

Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.